package LeetCode;

public class TestNum206 {
    //    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    // 1.头插法
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        } else {
//            //至少两个节点
//            ListNode dummyHead = new ListNode(5001);
//            // 边遍历原链表，边头插新链表
//            while (head!=null){
//                ListNode node =new ListNode(head.val);
//                node.next=dummyHead.next;
//                dummyHead.next=node;
//                head=head.next;
//            }
//            return dummyHead.next;
//        }
//    }
    //2.原地移动.
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        } else {
//            //至少两个节点
//            ListNode prev = null;
//            ListNode cur = head;
//            while (cur != null) {
//                ListNode next = cur.next;
//                cur.next=prev;
//                prev=cur;
//                cur=next;
//            }
//            return prev;
//        }
//    }
    //3.递归
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode sec = head.next;
        ListNode newHead = reverseList(sec);
        sec.next=head;
        head.next=null;
        return newHead;
    }
}
